#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
    freopen("in.txt","r", stdin);
    int n, m;
    cin >> n >> m;
    vector<pair<int,int> >* a = new vector<pair<int,int> >[n+1];
    for (int i = 0; i < m; i++) {
        int v1, v2,p;
        cin >> v1 >> v2 >> p;
        a[v1].push_back(make_pair(v2,p));
        a[v2].push_back(make_pair(v1,p));
    }
    int k;
    cin >> k;
    int shortestDist = INT_MAX;
    int shortPathId = 0;
    for (int i = 0; i < k; i++) {
        int s;
        cin >> s;
        unsigned char visit[n+1] = {};
        int first, now;
        int dist = 0;
        cin >> first;
        visit[first]++;
    	visit[0] = first;
    	bool isNA = false;
        for (int j = 1; j < s; j++) {            
            cin >> now;
  			if( !isNA ){
	            int kk;
	            for (kk = 0; kk < a[first].size(); kk++) {
	                if (a[first][kk].first == now) {                   
	                    dist += a[first][kk].second;
	                    visit[now]++;
	                    break;
	                }
	            }
	            if( kk==a[first].size() ) isNA = true;
				first = now;
        	}
        }
        if( isNA ){
        	cout <<"Path " << i+1 << ": NA (Not a TS cycle)\n";
		}else{
			int j = 1;
			for(; j<n+1; j++) if( visit[j]==0 ) break;
			if( j==n+1 && visit[visit[0]]>1 ){
				if( visit[visit[0]]==2 ) cout <<"Path " << i+1 << ": "<< dist <<" (TS simple cycle)\n";
				else cout <<"Path " << i+1 << ": "<< dist <<" (TS cycle)\n";
				if ( dist < shortestDist) {
		            shortestDist = dist;
		            shortPathId = i + 1;
		        }
			}else cout <<"Path " << i+1 << ": "<< dist <<" (Not a TS cycle)\n";
		}
    }
    cout << "Shortest Dist(" << shortPathId << ") = "<< shortestDist;
    return 0;
}

